<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=9"/>
<title>Radix-8 Complex FFT Functions</title>
<title>CMSIS-DSP: Radix-8 Complex FFT Functions</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<link href="cmsis.css" rel="stylesheet" type="text/css" />
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="dynsections.js"></script>
<script type="text/javascript" src="printComponentTabs.js"></script>
<link href="navtree.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="resize.js"></script>
<script type="text/javascript" src="navtree.js"></script>
<script type="text/javascript">
  $(document).ready(initResizable);
</script>
<link href="search/search.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="search/search.js"></script>
<script type="text/javascript">
  $(document).ready(function() { searchBox.OnSelectItem(0); });
</script>
<link href="stylsheetf" rel="stylesheet" type="text/css" />
</head>
<body>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
 <tbody>
 <tr style="height: 46px;">
  <td id="projectlogo"><img alt="Logo" src="CMSIS_Logo_Final.png"/></td>
  <td style="padding-left: 0.5em;">
   <div id="projectname">CMSIS-DSP
   &#160;<span id="projectnumber">Version 1.4.7</span>
   </div>
   <div id="projectbrief">CMSIS DSP Software Library</div>
  </td>
 </tr>
 </tbody>
</table>
</div>
<!-- end header part -->
<div id="CMSISnav" class="tabs1">
    <ul class="tablist">
      <script type="text/javascript">
		<!--
		writeComponentTabs.call(this);
		//-->
      </script>
	  </ul>
</div>
<!-- Generated by Doxygen 1.8.2 -->
<script type="text/javascript">
var searchBox = new SearchBox("searchBox", "search",false,'Search');
</script>
  <div id="navrow1" class="tabs">
    <ul class="tablist">
      <li><a href="index.html"><span>Main&#160;Page</span></a></li>
      <li><a href="pages.html"><span>Usage&#160;and&#160;Description</span></a></li>
      <li><a href="modules.html"><span>Reference</span></a></li>
      <li>
        <div id="MSearchBox" class="MSearchBoxInactive">
        <span class="left">
          <img id="MSearchSelect" src="search/mag_sel.png"
               onmouseover="return searchBox.OnSearchSelectShow()"
               onmouseout="return searchBox.OnSearchSelectHide()"
               alt=""/>
          <input type="text" id="MSearchField" value="Search" accesskey="S"
               onfocus="searchBox.OnSearchFieldFocus(true)" 
               onblur="searchBox.OnSearchFieldFocus(false)" 
               onkeyup="searchBox.OnSearchFieldChange(event)"/>
          </span><span class="right">
            <a id="MSearchClose" href="javascript:searchBox.CloseResultsWindow()"><img id="MSearchCloseImg" border="0" src="search/close.png" alt=""/></a>
          </span>
        </div>
      </li>
    </ul>
  </div>
</div><!-- top -->
<div id="side-nav" class="ui-resizable side-nav-resizable">
  <div id="nav-tree">
    <div id="nav-tree-contents">
      <div id="nav-sync" class="sync"></div>
    </div>
  </div>
  <div id="splitbar" style="-moz-user-select:none;" 
       class="ui-resizable-handle">
  </div>
</div>
<script type="text/javascript">
$(document).ready(function(){initNavTree('group___radix8___c_f_f_t___c_i_f_f_t.html','');});
</script>
<div id="doc-content">
<!-- window showing the filter options -->
<div id="MSearchSelectWindow"
     onmouseover="return searchBox.OnSearchSelectShow()"
     onmouseout="return searchBox.OnSearchSelectHide()"
     onkeydown="return searchBox.OnSearchSelectKey(event)">
<a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(0)"><span class="SelectionMark">&#160;</span>All</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(1)"><span class="SelectionMark">&#160;</span>Data Structures</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(2)"><span class="SelectionMark">&#160;</span>Files</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(3)"><span class="SelectionMark">&#160;</span>Functions</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(4)"><span class="SelectionMark">&#160;</span>Variables</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(5)"><span class="SelectionMark">&#160;</span>Typedefs</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(6)"><span class="SelectionMark">&#160;</span>Enumerations</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(7)"><span class="SelectionMark">&#160;</span>Enumerator</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(8)"><span class="SelectionMark">&#160;</span>Macros</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(9)"><span class="SelectionMark">&#160;</span>Groups</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(10)"><span class="SelectionMark">&#160;</span>Pages</a></div>

<!-- iframe showing the search results (closed by default) -->
<div id="MSearchResultsWindow">
<iframe src="javascript:void(0)" frameborder="0" 
        name="MSearchResults" id="MSearchResults">
</iframe>
</div>

<div class="header">
  <div class="headertitle">
<div class="title">Radix-8 Complex FFT Functions</div>  </div>
<div class="ingroups"><a class="el" href="group__group_transforms.html">Transform Functions</a></div></div><!--header-->
<div class="contents">
<dl class="section user"><dt></dt><dd>Complex Fast Fourier Transform(CFFT) and Complex Inverse Fast Fourier Transform(CIFFT) is an efficient algorithm to compute Discrete Fourier Transform(DFT) and Inverse Discrete Fourier Transform(IDFT). Computational complexity of CFFT reduces drastically when compared to DFT. </dd></dl>
<dl class="section user"><dt></dt><dd>This set of functions implements CFFT/CIFFT for floating-point data types. The functions operates on in-place buffer which uses same buffer for input and output. Complex input is stored in input buffer in an interleaved fashion.</dd></dl>
<dl class="section user"><dt></dt><dd>The functions operate on blocks of input and output data and each call to the function processes <code>2*fftLen</code> samples through the transform. <code>pSrc</code> points to In-place arrays containing <code>2*fftLen</code> values. </dd></dl>
<dl class="section user"><dt></dt><dd>The <code>pSrc</code> points to the array of in-place buffer of size <code>2*fftLen</code> and inputs and outputs are stored in an interleaved fashion as shown below. <pre> {real[0], imag[0], real[1], imag[1],..} </pre></dd></dl>
<dl class="section user"><dt>Lengths supported by the transform: </dt><dd></dd></dl>
<dl class="section user"><dt></dt><dd>Internally, the function utilize a Radix-8 decimation in frequency(DIF) algorithm and the size of the FFT supported are of the lengths [ 64, 512, 4096].</dd></dl>
<dl class="section user"><dt>Algorithm: </dt><dd></dd></dl>
<p><b>Complex Fast Fourier Transform:</b> </p>
<dl class="section user"><dt></dt><dd>Input real and imaginary data: <pre>    
x(n) = xa + j * ya    
x(n+N/4 ) = xb + j * yb    
x(n+N/2 ) = xc + j * yc    
x(n+3N 4) = xd + j * yd    
</pre> where N is length of FFT </dd></dl>
<dl class="section user"><dt></dt><dd>Output real and imaginary data: <pre>    
X(4r) = xa'+ j * ya'    
X(4r+1) = xb'+ j * yb'    
X(4r+2) = xc'+ j * yc'    
X(4r+3) = xd'+ j * yd'    
</pre> </dd></dl>
<dl class="section user"><dt></dt><dd>Twiddle factors for Radix-8 FFT: <pre>    
Wn = co1 + j * (- si1)    
W2n = co2 + j * (- si2)    
W3n = co3 + j * (- si3)    
</pre></dd></dl>
<dl class="section user"><dt></dt><dd><div class="image">
<img src="CFFT.gif" alt="CFFT.gif"/>
<div class="caption">
Radix-8 Decimation-in Frequency Complex Fast Fourier Transform</div></div>
</dd></dl>
<dl class="section user"><dt></dt><dd>Output from Radix-8 CFFT Results in Digit reversal order. Interchange middle two branches of every butterfly results in Bit reversed output. </dd></dl>
<dl class="section user"><dt></dt><dd><b> Butterfly CFFT equations:</b> <pre>    
xa' = xa + xb + xc + xd    
ya' = ya + yb + yc + yd    
xc' = (xa+yb-xc-yd)* co1 + (ya-xb-yc+xd)* (si1)    
yc' = (ya-xb-yc+xd)* co1 - (xa+yb-xc-yd)* (si1)    
xb' = (xa-xb+xc-xd)* co2 + (ya-yb+yc-yd)* (si2)    
yb' = (ya-yb+yc-yd)* co2 - (xa-xb+xc-xd)* (si2)    
xd' = (xa-yb-xc+yd)* co3 + (ya+xb-yc-xd)* (si3)    
yd' = (ya+xb-yc-xd)* co3 - (xa-yb-xc+yd)* (si3)    
</pre></dd></dl>
<dl class="section user"><dt></dt><dd>where <code>fftLen</code> length of CFFT/CIFFT; <code>ifftFlag</code> Flag for selection of CFFT or CIFFT(Set ifftFlag to calculate CIFFT otherwise calculates CFFT); <code>bitReverseFlag</code> Flag for selection of output order(Set bitReverseFlag to output in normal order otherwise output in bit reversed order); <code>pTwiddle</code>points to array of twiddle coefficients; <code>pBitRevTable</code> points to the array of bit reversal table. <code>twidCoefModifier</code> modifier for twiddle factor table which supports all FFT lengths with same table; <code>pBitRevTable</code> modifier for bit reversal table which supports all FFT lengths with same table. <code>onebyfftLen</code> value of 1/fftLen to calculate CIFFT;</dd></dl>
<dl class="section user"><dt>Fixed-Point Behavior </dt><dd>Care must be taken when using the fixed-point versions of the CFFT/CIFFT function. Refer to the function specific documentation below for usage guidelines. </dd></dl>
</div><!-- contents -->
</div><!-- doc-content -->
<!-- start footer part -->
<div id="nav-path" class="navpath"><!-- id is needed for treeview function! -->
  <ul>
    <li class="footer">Generated on Tue Oct 27 2015 14:35:33 for CMSIS-DSP by ARM Ltd. All rights reserved.
	<!--
    <a href="http://www.doxygen.org/index.html">
    <img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.8.2 
	-->
	</li>
  </ul>
</div>
</body>
</html>
